package com.fwpsl.dynamicprogramming;

import java.util.Arrays;

/**
 * @author: 风戏fw
 * @date: 2024/4/8
 * @description: 背包问题： 给定一组物品，每种物品都有自己的重量和价值，在限定的总重量内，如何选择，才能使得物品的总价值最大。
 * 背包问题有多种变种，每种变种都有其特定的约束条件和优化目标。以下是几种常见的背包问题：
 * 1. 0-1背包问题：每种物品只有一个，可以选择放或不放入背包中。
 * 2. 完全背包问题：每种物品的数量是无限的，可以选择放入任意多个该物品。
 * 3. 多重背包问题：每种物品有一定的数量限制，即每种物品可以选择放入0个到其数量限制内的任意多个。
 * 4. 分组背包问题：物品被分为若干组，每组内的物品是互斥的（即只能选择组内的一个物品或者不选），同时还有一个总重量限制。
 * <p>
 * 解决背包问题的方法多种多样，包括但不限于动态规划、回溯法、分支限界法等。
 * 其中，动态规划是解决背包问题最常用的方法，特别是0-1背包问题和完全背包问题。
 * <p>
 * 注意： 背包问题是一类NP完全问题，当问题规模较大时，可能无法找到多项式时间复杂度的算法来求解。
 * 在实际应用中，可能需要结合问题的具体特点和需求，采用启发式算法、近似算法或者其他优化技术来求解。
 * <p>
 * 解题模板： 背包问题大体的解题模板是两层循环，分别遍历物品nums和背包容量target，然后写转移方程，
 * 根据背包的分类我们确定物品和容量遍历的先后顺序，根据问题的分类我们确定状态转移方程的写法。
 */
public class KnapsackProblem {

    /**
     * 0-1背包问题是一种组合优化的NP完全问题，其中每种物品只有一个，可以选择放入背包或不放入背包。
     * 目标是选择一些物品放入一个固定容量的背包中，使得背包内物品的总价值最大，同时不超过背包的总重量限制。
     * <p>
     * dp[i][j]=max(dp[i-1][j], dp[i-1][j-w[i]]+v[i]);
     *
     * @param weights
     * @param values
     * @param capacity
     * @return
     */
    public static int knapsack01(int[] weights, int[] values, int capacity) {
        // 物品数量
        int n = weights.length;
        // 初始化二维数组dp，dp[i][j]表示考虑前i个物品时，在容量为j的背包中能够获得的最大价值。
        int[][] dp = new int[n + 1][capacity + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= capacity; j++) {
                if (weights[i - 1] <= j) {
                    // 不放入物品i的最大价值： dp[i - 1][j]
                    // 放入物品i的最大价值： dp[i - 1][j - weights[i - 1]] + values[i - 1],
                    // dp[i - 1][j - weights[i - 1]]表示不包含当前物品的最大价值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weights[i - 1]] + values[i - 1]);
                } else {
                    // 当前物品重量大于背包剩余容量，则不放入该物品
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }

        // dp[n][capacity]存储了背包容量为capacity时的最大价值
        return dp[n][capacity];
    }

    /**
     * 01背包问题优化： 将二维数组降为一维。（注意：容量循环需要倒序）
     * <p>
     * dp[j]=max(dp[j], dp[j-w[i]]+v[i]);
     *
     * @param weights
     * @param values
     * @param capacity
     * @return
     */
    public static int knapsack01_2(int[] weights, int[] values, int capacity) {
        // 物品数量
        int n = weights.length;
        // 初始化一维数组dp
        int[] dp = new int[capacity + 1];

        for (int i = 0; i < n; i++) {
            for (int j = capacity; j >= weights[i]; j--) {
                // 不放入物品i的最大价值： dp[j]
                // 放入物品i的最大价值： dp[j - weights[i]] + values[i],
                // j - weights[i]表示背包放了物品i的剩余容量； dp[j - weights[i]]表示不包含当前物品的最大价值
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }

        // dp[capacity]存储了背包容量为capacity时的最大价值
        return dp[capacity];
    }

    /**
     * 完全背包问题与0-1背包问题的区别在于每种物品的数量是无限的，即每种物品可以选择放入0个或多个。
     * 在动态规划的实现上，完全背包问题可以通过一维数组来优化空间复杂度，并且状态转移方程也有所不同。
     * <p>
     * f[j]=max(f[j], f[j-w[i]]+v[i]);
     *
     * @param weights
     * @param values
     * @param capacity
     * @return
     */
    public static int completeKnapsack(int[] weights, int[] values, int capacity) {
        // 物品数量
        int n = weights.length;
        // 使用一维数组优化空间
        int[] dp = new int[capacity + 1];

        // 动态规划填表
        for (int i = 0; i < n; i++) {
            for (int j = weights[i]; j <= capacity; j++) {
                // 不放入物品i的最大价值： dp[j]
                // 放入物品i的最大价值： dp[j - weights[i]] + values[i],
                // j - weights[i]表示背包放了物品i的剩余容量； dp[j - weights[i]]表示不包含当前物品的最大价值
                dp[j] = Math.max(dp[j], dp[j - weights[i]] + values[i]);
            }
        }

        // dp[capacity]存储了背包容量为capacity时的最大价值
        return dp[capacity];
    }

    /**
     * 多重背包问题可以通过二进制分组的方式转化为0-1背包问题来求解。具体地，我们可以将每种物品的数量拆分成多个不同的组合，
     * 使得这些组合能够表示出原数量的所有可能取值。这样，我们就可以将每个组合视为一个独立的物品，从而使用0-1背包的解法来求解。
     *
     * @param weights
     * @param values
     * @param counts
     * @param capacity
     * @return
     */
    public static int multipleKnapsack(int[] weights, int[] values, int[] counts, int capacity) {
        // 物品数量
        int n = weights.length;

        // 新数组的长度
        int newLength = 0;
        for (int i = 0; i < counts.length; i++) {
            for (int j = 0; (int) Math.pow(2, j) <= counts[i]; j++) {
                newLength++;
            }
        }

        // 转化后的物品重量数组
        int[] newWeights = new int[newLength];
        // 转化后的物品价值数组
        int[] newValues = new int[newLength];
        // 转化后数组的索引
        int index = 0;

        // 将多重背包转化为0-1背包（二进制分组）
        for (int i = 0; i < n; i++) {
            // 当前物品剩余数量
            int remain = counts[i];
            // 每次取当前剩余数量的二进制表示中的最高位
            for (int k = 1; k <= remain; k <<= 1) {
                newWeights[index] = k * weights[i];
                newValues[index] = k * values[i];
                remain -= k;
                index++;
            }
            // 如果剩余数量不是2的幂，则剩余部分单独作为一个物品
            if (remain > 0) {
                newWeights[index] = remain * weights[i];
                newValues[index] = remain * values[i];
                index++;
            }
        }

        // 0-1背包问题的求解
        return knapsack01_2(newWeights, newValues, capacity);
    }

    /**
     * 分组背包问题是指每种物品被划分为若干组，每组中的物品互斥，即每组至多选择一个物品放入背包中。
     * 求解分组背包问题可以使用动态规划的方法。
     *
     * @param weightGroup
     * @param valueGroup
     * @param capacity
     * @return
     */
    public static int groupKnapsack(int[][] weightGroup, int[][] valueGroup, int capacity) {
        // 组数
        int n = weightGroup.length;
        // 动态规划数组
        int[] dp = new int[capacity + 1];

        // 遍历每一组物品
        for (int i = 0; i < n; i++) {
            // 当前组的物品重量
            int weights[] = weightGroup[i];
            // 当前组的物品价值
            int values[] = valueGroup[i];
            // 当前组内的物品数量
            int m = weights.length;

            // 遍历背包容量，从大到小更新dp数组
            for (int j = capacity; j >= 0; j--) {
                // 遍历当前组内的每个物品
                for (int k = 0; k < m; k++) {
                    // 如果当前物品可以放入背包，则更新dp数组
                    if (j >= weights[k]) {
                        // 不放入物品i的最大价值： dp[j]
                        // 放入物品i的最大价值： dp[j - weights[i]] + values[i],
                        // j - weights[i]表示背包放了物品i的剩余容量； dp[j - weights[i]]表示不包含当前物品的最大价值
                        dp[j] = Math.max(dp[j], dp[j - weights[k]] + values[k]);
                    }
                }
            }
        }

        // 返回背包内的最大价值
        return dp[capacity];
    }

    public static void main(String[] args) {
        // 物品的重量
        int[] weights = {2, 3, 1, 5};
        // 物品的价值
        int[] values = {3, 4, 5, 6};
        // 背包的总容量
        int capacity = 11;
        int maxValue = 0;

        // ------------------------- 01背包问题 -------------------------
        maxValue = knapsack01(weights, values, capacity);
        System.out.println("0 - 1背包内的最大价值为: " + maxValue);

        maxValue = knapsack01_2(weights, values, capacity);
        System.out.println("0 - 1背包内的最大价值为: " + maxValue);


        // ------------------------- 完全背包问题 -------------------------
        maxValue = completeKnapsack(weights, values, capacity);
        System.out.println("完全背包内的最大价值为: " + maxValue);


        // ------------------------- 多重背包问题 -------------------------
        // 物品的数量限制
        int[] counts = {3, 4, 5, 2};

        maxValue = multipleKnapsack(weights, values, counts, capacity);
        System.out.println("多重背包内的最大价值为: " + maxValue);


        // ------------------------- 分组背包问题 -------------------------
        // 每组物品的重量和价值
        int[][] weightGroup = {{2, 3, 4}, {1, 2}};
        int[][] valueGroup = {{3, 5, 5}, {2, 3}};

        maxValue = groupKnapsack(weightGroup, valueGroup, capacity);
        System.out.println("分组背包内的最大价值为: " + maxValue);
    }
}
